package base;

import java.util.Arrays;

/**
 * [1,3,6,7,9,4,10,5,6]
 *
 * @author mazouri
 * @create 2021-12-28 10:49
 */
public class _2_lengthOfLIS_dp {
    public int lengthOfLIS(int[] nums) {
        int max=1;
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] > nums[i])  dp[i] = Math.max( dp[i], dp[j]+1);
            }

            max = Math.max(dp[i], max);
        }

        return max;
    }

    public static void main(String[] args) {
        _2_lengthOfLIS_dp o = new _2_lengthOfLIS_dp();
        System.out.println(o.lengthOfLIS(new int[]{1,3,6,7,9,4,10,5,6}));
    }
}
